package tianhao.luo.algorithm;

/**
 * 动态规划背包问题
 * @author: tianhao.luo@hand-china.com 2021/6/30  下午8:58
 */
public class KnapsackProblem {
    /**
     * 物品重量
     */
    int[] w = {1,4,3};
    /**
     * 物品的价值
     */
    int[] value = {1500,3000,2000};
    /**
     * 背包的容量
     */
    int m = 4;
    /**
     * 物品的个数
     */
    int n = value.length;

    /**
     * 为了记录放入商品的情况,我们定义一个二维数组
     */
    int[][] path = new int[n+1][m+1];

    /**
     * v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
     */
    int[][] v = new int[n+1][m+1];


    {
        // 初始化第一行和第一列,这里在本程序中,可以不处理,默认为0
        for (int i = 0; i < v.length; i++) {
            // 将第一列设置为0
            v[i][0] = 0;
        }

        for (int i = 0; i < v[0].length; i++) {
            // 将第一行设置为0
            v[0][i] = 0;
        }

        // 动态规划
        // 不处理第一行
        for (int i = 1; i < v.length; i++) {
            // 不处理第一列
            for (int j = 1; j < v[0].length; j++) {
                // 公式
                // 因为程序的i是从1开始,因此公式中的w[i]要修改为w[i-1]
                if (w[i-1] > j){
                    v[i][j] = v[i-1][j];
                }else {
                    // 因为程序中i是从1开始的,因此公式需要调整为下面的代码
                    v[i][j] = Math.max(v[i-1][j],value[i-1]+v[i-1][j-w[i-1]]);
                    // 为了记录商品存放到背包的情况,我们不能直接使用上面的公式;需要添加一个判断,手动记录一下放入的商品
                    if (v[i-1][j]<value[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j] = value[i-1]+v[i-1][j-w[i-1]];
                        // 把当前情况记录
                        path[i][j] =1;
                    }else {
                        v[i][j] =v[i-1][j];
                    }
                }
            }
        }


        // 输出
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }

        // 输出最终是放入的那些商品
        // 下面的输出会把所有的放入情况都得到,我们只需要最后的放入情况
//        for (int i = 0; i < path.length; i++) {
//            for (int j = 0; j < path[i].length; j++) {
//                if (path[i][j] ==1){
//                    System.out.printf("第%d个商品放入了背包\n",i);
//                }
//            }
//        }

        // 行的最大下标
        int i = path.length -1;
        // 列的最大下标
        int j = path[0].length -1;
        // 从path数组的最后开始找
        while (i > 0 && j >0){
            if (path[i][j] > 0){
                System.out.printf("第%d个商品放入了背包\n",i);
                j = j - w[i-1];
            }
            i--;
        }
    }
}
